﻿#define _CRT_SECURE_NO_WARNINGS 1 

//打印素数
//使用C语言写⼀个程序打印100~200之间的素数，数字中间使用空格分割。
//素数是指只能被1和它本身整除的正整数

#include <stdio.h>
#include <math.h> //使用sqrt函数所需要包含的头文件

int main()
{
	int i = 0;
	int j = 0;

	//第一种方法，暴力破解
	for (i = 100; i <= 200; i++)
	{
		int flag = 1;//定义变量记录当前数是否为素数，假设是素数，变量值为1

		//利用j来判断是否是素数,遍历2~当前数-1
		for (j = 2; j < i; j++)
		{
			//存在⼀个数可以整除当前数
			if (i % j == 0)
			{
				flag = 0;//不是素数
				break;
			}
		}

		if (flag == 1)//是素数就打印
			printf("%d ", i);
	}

	printf("\n");

	//第二种优化思路
	//素数一定是奇数，奇数不一定是素数
	for (i = 101; i <= 200; i += 2)//每次相加2
	{
		int flag = 1;//定义变量记录当前数是否为素数，假设是素数，变量值为1

		for (j = 2; j < i; j++)
		{
			if (i % j == 0)
			{
				flag = 0;//不是素数
				break;
			}
		}

		if (flag == 1)//是素数就打印
			printf("%d ", i);
	}

	printf("\n");

	//第三种 2 到 x-1 中存在某个数 t 可以整除 x 时，令 d=x/t，则 d 也可以整除 x，并且结果为 t。因
	//此，当 2~√x 中不存在可以整除 x 的数时，√x + 1~x 也不存在可以整除 x 的数。

	for (i = 101; i <= 200; i += 2)//每次相加2
	{
		int flag = 1;//定义变量记录当前数是否为素数，假设是素数，变量值为1

		for (j = 2; j <= sqrt(i); j++)
		{
			if (i % j == 0)
			{
				flag = 0;//不是素数
				break;
			}
		}

		if (flag == 1)//是素数就打印
			printf("%d ", i);
	}

	return 0;
}


//扩展： 用筛选法求100之内的素数并输出。
#include <stdio.h>

int main()
{
	int i = 0;
	int j = 0;
	int arr[100] = { 0 };//初始化数组

	//100不是素数所以不赋值
	for (i = 0; i < 100; i++)
	{
		arr[i] = i + 1;
	}

	//1不是素数,把0赋值给数组第一个
	arr[0] = 0;

	for (i = 0; i < 100; i++)
	{
		//如果它不是素数则不执行后面的代码
		if (arr[i] == 0)
			continue;

		// 位置之后的所有数据去模a[i]位置的数字
		// 如果能够整除则一定不是素数，该位置数据用0填充
		for (j = i + 1; j < 100; j++)
		{
			if (arr[j] != 0)
			{
				if (arr[j] % arr[i] == 0)//如果后面的数字模前面留下的数字等于0，那么这个数字一定不是素数
					arr[j] = 0;
				//把这个位置用0替代
			}
		}
	}

	for (i = 0; i < 100; i++)
	{
		if (arr[i] != 0)
			printf("%d ", arr[i]);
	}
	return 0;
}
